#!/usr/bin/python
#***************************************************************************
# Copyright notice for this file:
#  Copyright (C) 2012 TheAxeMan
#  _______ _                               _    _
# |__   __| |     ___     /\          ___ | \  / |
#    | |  | |__  / _ \   /  \  __  _ / _ \|  \/  | __ _ _ __
#    | |  | '_ \|  __/  / /\ \ \ \/ |  __/| .  . |/ _` | '_ \
#    | |  | | | | (__/\/ ____ \ )  (| (__/| |\/| | (_| | | | |
#    |_|  |_| |_|\____/_/    \_._/\_.\____|_|  |_|\__,_|_| |_|
#
# Final Fantasy TAS scripts by TheAxeMan
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#
#***************************************************************************

import sys
import re
import string

#need this for area name translation
from gamedata import GameData
from rundata import RunSegment
from rundata import RunSegments


"""
This class represents a segment of a run with some information
on what parameters to check in the regression.

attribute notes:
  do_power_cycle makes everything else meaningless
  To make things easier, try_power_cycle and extra steps aren't both allowed

attributes:
  area_id - Id of area for where this takes place. Might not matter.
  base_steps - base steps that will be taken
  extra_steps - extra steps to try taking
  do_power_cycle - if True, this is just a power cycle. Ignore all
                   other attributes
  try_option - this set of steps is an all-or-nothing option.
  option_id - id of option to support tying two or more together
  option_cost - cost specified for the option. Can be overridded by a declaration
  try_power_cycle - Try using a power cycle somewhere in this segment.
  note - some text that can go in the output
"""
class MetaRunSegment:
  def __init__(self, area_id=0, base_steps=0, note=""):
    self.area_id = area_id
    self.base_steps = base_steps
    self.do_power_cycle = (note == "power cycle")
    self.try_power_cycle = False
    self.try_option = False
    self.option_id = 0
    self.option_cost = 0
    self.extra_steps = 0
    self.note = note
    self.permutation_count = 0

  def isPowerCycle(self):
    """Quick check to see if this is just a power cycle"""
    return self.do_power_cycle

  def loadString(self, input_string, gdata):
    #check for do_power_cycle
    match = re.search("(?:\-)?do_power_cycle", input_string)
    if match:
      self.do_power_cycle = True
      #nothing else matters
      return

    #check for note
    match = re.search("^\s*note\s+", input_string)
    if match:
      self.note = input_string[match.end():].strip()
      return

    #read base steps
    match = re.search("^\s*\d+", input_string)
    if not match:
      print "invalid input:", input_string
      sys.exit()
    self.base_steps = int(match.group())
    remaining_text = input_string[match.end():].strip()

    #check for option
    match = re.search("(?:\-)?try_option\s+(\S+)(?:\s+(-?\d+))?", remaining_text)
    if match:
      self.try_option = True
      self.option_id = match.group(1)
      #remove matched string
      remaining_text = re.sub(match.group(), "", remaining_text).strip()
      if match.group(2) == None:
        self.option_cost = 0
      else:
        self.option_cost = int(match.group(2))

    #check for extra steps
    match = re.search("(?:\-)?try_extra\s+(\d+)", remaining_text)
    if match:
      self.extra_steps = int(match.group(1))
      #remove matched string
      remaining_text = re.sub(match.group(), "", remaining_text).strip()
    
    #check for try_power_cycle
    match = re.search("(?:\-)?try_power_cycle", remaining_text)
    if match:
      self.try_power_cycle = True
      #remove matched string
      remaining_text = re.sub(match.group(), "", remaining_text).strip()

    #remaining text is area name
    self.area_id = gdata.translateAreaName(remaining_text)
    return

  def makeString(self, gdata, use_area_name=False):
    description = ""

    if self.do_power_cycle:
      description += "power cycle"
    elif self.base_steps + self.extra_steps > 0:
      description += str(self.base_steps)
      if self.extra_steps > 0:
        description += " to " + str(self.base_steps+self.extra_steps)
      description += " in area "
      if use_area_name:
        description += gdata.getAreaName(self.area_id)
      else:
        description += str(self.area_id)
      if self.try_power_cycle:
        description += " with a possible power cycle"
      if self.try_option:
        description += " tied to option " + str(self.option_id)
    elif self.note != "":
      description += "*** " + self.note + " ***"
    else:
      description += "!!! Seems to be a badly formed segment !!!"

    return description

  def permutationCount(self):
    """Calculate number of permutations for this metaseg"""
    #return recorded value if nonzero
    if self.permutation_count > 0: return self.permutation_count

    num = 1 #always at least one...
    num *= self.extra_steps + 1 #consider extra steps
    if self.try_power_cycle:
      num *= self.base_steps + 2 #not cycling power is also possible
    self.permutation_count = num
    return num
 
  def makeRunSegments(self, seed, insert_notes):
    """Create a RunSegments structure from this meta-seg"""
    run_segs = RunSegments()
    if self.do_power_cycle:
      run_segs.addPowerCycle()
    elif self.try_power_cycle:
      #use seed-1 as number of steps before power cycle
      #for seed==0, don't do power cycle
      if seed > self.base_steps + 1:
        print "error: bad seed",seed,"for try_power_cycle"
        print "expected seed between 0 and",self.base_steps+1
        sys.exit()
      if insert_notes:
        run_segs.addNote("trying power cycle with seed "+str(seed))
      if self.base_steps == 0 and self.try_power_cycle:
        #supports trying a power cycle with no base_steps
        if seed > 0:
          run_segs.addPowerCycle()
      elif seed == 0:
        #no power cycle
        segment = RunSegment(self.area_id, self.base_steps)
        run_segs.addSegment(segment)
      elif seed == 1:
        #power cycle, then steps
        first_segment = RunSegment()
        first_segment.setPowerCycle()
        second_segment = RunSegment(self.area_id, self.base_steps)
        run_segs.addSegment(first_segment)
        run_segs.addSegment(second_segment)
      elif seed == self.base_steps+1:
        #take all steps then power cycle
        first_segment = RunSegment(self.area_id, self.base_steps)
        second_segment = RunSegment()
        second_segment.setPowerCycle()
        run_segs.addSegment(first_segment)
        run_segs.addSegment(second_segment)
      else:
        #some steps, power cycle, then some more steps
        first_segment = RunSegment(self.area_id, seed-1)
        second_segment = RunSegment()
        second_segment.setPowerCycle()
        third_segment = RunSegment(self.area_id, self.base_steps-(seed-1))
        run_segs.addSegment(first_segment)
        run_segs.addSegment(second_segment)
        run_segs.addSegment(third_segment)
    elif self.extra_steps > 0:
      #seed is number of extra steps
      if seed > self.extra_steps:
        print "error: bad seed",seed,"for try_extra_steps"
        print "expected seed between 0 and",self.extra_steps
        sys.exit()
      if insert_notes:
        run_segs.addNote("trying "+str(seed)+" extra steps")
      #don't bother adding segment unless there are steps taken
      #this allows extra steps with no base steps
      if self.base_steps + seed > 0:
        segment = RunSegment(self.area_id, self.base_steps + seed)
        run_segs.addSegment(segment)
    else:
      #just the base steps, no regression items
      if seed > 0:
        print "error: nonzero seed",seed,"for non-regressable segment"
        sys.exit()
      if self.base_steps > 0:
        segment = RunSegment(self.area_id, self.base_steps)
        run_segs.addSegment(segment)
      elif insert_notes and self.note != "":
        run_segs.addNote(self.note)
    return run_segs
      

"""
This is basically just a list of MetaRunSegments representing a run.

attributes:
  run - list of MetaRunSegments forming the run
  option_flags - list of True/False flags indicating which options are selected
* option_set - list of flags indicating if the option has been set previously.
  option_costs - Cost of each option, not including the step cost.
                Probably negative since the steps can't be negative.
  option_names - names of each option, to be used in pretty result output
  option_ids - id for each option name
  last_seed - last seed used to generate run. options reflect this
"""
class MetaRunSegments:
  def __init__(self):
    self.clear()
  def clear(self):
    self.run = []
    self.option_flags = []
    self.option_costs = []
    self.option_names = []
    self.option_set = []
    self.option_ids = {}
    self.last_seed = 0

  def resetOptionSet(self, value=False):
    for i in range(len(self.option_set)):
      self.option_set[i] = value

  def addSegment(self, segment):
    """Adds segment to list but does not update option list!"""
    self.run.append(segment)
  def addSegments(self, segments):
    """
    Adds segments to end of list. The argument will have
    an empty list on finishing. Does not update option list!
    """
    while(len(segments.run) > 0):
      self.run.append(segments.run.pop(0))

  def splitOnFirstRegression(self, split_before=True):
    """Splits the metarun into two parts such that the first regression
       item in the original run is either the first metaseg in the
       second part or the last in the first part.
       The calling metarun retains this first part and returns a new
       metarun with the second. If there are no regressable items, the
       second list is empty.
       The argument controls whether the first regressable segment is
       in the first or second part.
    """
    split_segs = MetaRunSegments()
    #copy some information
    split_segs.option_flags = self.option_flags[:]
    split_segs.option_set = self.option_set[:]
    #other info is all right to copy by reference
    split_segs.option_costs = self.option_costs
    split_segs.option_names = self.option_names
    split_segs.option_ids = self.option_ids

    temp_segs = []
    while(len(self.run) > 0):
      metaseg = self.run[0]
      if not split_before:
        temp_segs.append(self.run.pop(0))
      if metaseg.try_power_cycle: break
      if metaseg.extra_steps > 0: break
      if metaseg.try_option and not self.option_set[metaseg.option_id]: break
      if split_before:
        temp_segs.append(self.run.pop(0))

    split_segs.run = self.run
    self.run = temp_segs
    return split_segs

  def totalBaseSteps(self):
    total = 0
    for segment in self.run:
      if not segment.try_option:
        total += segment.base_steps
    return total

  def totalMaxSteps(self):
    total = 0
    for segment in self.run:
      if segment.base_steps >= 0:
        total += segment.base_steps + segment.extra_steps
    return total

  def permutationCount(self, debug=False):
    num = 1
    #double for each unset option
    for op_set in self.option_set:
      if not op_set:
        num *= 2
    if debug: print "pcount from options is",num
    #all other regression types
    for segment in self.run:
      num *= segment.permutationCount()
      if debug: print "pcount is",num
    return num

  def makeRunSegments(self, seed, insert_notes=False, reset_option_set=True, print_junk=False):
    """
    Generate RunSegments from a metarun. The seed is used such that
    the leaves of the tree are numerically consecutive.
    Reset_option_set should be False when the metarun only represents
    part of a full run.
    """
    self.last_seed = seed
    run_segs = RunSegments()
    #reset all option_set flags to False
    #necessary to get accurate pcount
    if reset_option_set:
      self.resetOptionSet()

    #get total permutations
    remaining_pcount = self.permutationCount()
    if print_junk:
      self.printRun(0)
      remaining_pcount = self.permutationCount(True)
      print "pcount to make seg is", remaining_pcount

    #now go through segments and do it
    for segment in self.run:
      #if we encounter an option that hasn't been set yet, do it
      if segment.try_option and not self.option_set[segment.option_id]:
        remaining_pcount = remaining_pcount / 2
        seg_seed = seed / remaining_pcount
        if seg_seed > 1:
          print "bad seed for setting option:", seg_seed
          sys.exit()
        seed = seed % remaining_pcount
        self.option_flags[segment.option_id] = (seg_seed == 1)
        self.option_set[segment.option_id] = True
        seg_seed = 0
      else:
        seg_pcount = segment.permutationCount()
        if seg_pcount > 1:
          remaining_pcount = remaining_pcount / seg_pcount
          seg_seed = seed / remaining_pcount
          seed = seed % remaining_pcount
        else:
          seg_seed = 0
      if insert_notes and segment.try_option:
        option_id = segment.option_id
        option_note = "option " + self.option_names[segment.option_id]
        if self.option_flags[segment.option_id]:
          run_segs.addNote(option_note + " is enabled")
        else:
          run_segs.addNote(option_note + " is disabled")
      if not segment.try_option or self.option_flags[segment.option_id]:
        add_segs = segment.makeRunSegments(seg_seed, insert_notes)
      else:
        add_segs = RunSegments()
      run_segs.addSegments(add_segs)

    #run_segs are complete!
    return run_segs

  def optionCosts(self):
    """We can't do this for an arbitrary seed anymore since
       options are no longer set upfront"""
    cost = 0
    for option_id in range(len(self.option_flags)):
      if self.option_flags[option_id]:
        cost += self.option_costs[option_id]
    return cost

  def printRun(self, gdata, use_area_names=False):
    """prints out details on a list of run segments"""
    for segment in self.run:
      print segment.makeString(gdata, use_area_names)

  def printOptionStatus(self):
    print "name   flag  set"
    for i in range(len(self.option_names)):
      print self.option_names[i], self.option_flags[i], self.option_set[i]

  def loadFromFile(self, filename, gdata):
    """load a run from a file. Format is:
       <stepcount> area_name [try_extra <extra_steps>] [try_power_cycle] [try_option <option_name>] |
       note <note> |
       do_power_cycle |
       option <option_name> [<option_cost>]
       Comments with #
    """
    self.clear()
    options_parsed = {}
    runfile = open(filename)
    for line in runfile:
      #strip comments
      line = re.sub("#.*", "", line)
      line = line.strip()
      if not re.search("\S", line):
        #move on if there's just whitespace
        continue
      #stop on a line with "quit"
      if line == "quit":
        break
      #parse option declarations here
      match = re.search("^\s*option\s+(\S+)", line)
      if match:
        option_name = match.group(1)
        #remove these strings then look for a number. That's the cost
        line = re.sub(match.group(), "", line).strip()
        match = re.search("-?\d+", line)
        if match:
          option_cost = int(match.group())
        else:
          #default option cost is 0
          option_cost = 0
        options_parsed[option_name] = option_cost
        continue

      segment = MetaRunSegment()
      segment.loadString(line, gdata)
      self.addSegment(segment)
    runfile.close()

    #resolve options here: remove unused options and translate names to ids
    #error on undeclared options
    next_option_id = 0
    for segment in self.run:
      if not segment.try_option: continue
      option_name = segment.option_id
      #make sure option was declared
      if option_name not in options_parsed:
        #add option with cost from the seg
        options_parsed[option_name] = segment.option_cost
        #warning probably overkill
        #print "Adding option", option_name,"at cost",segment.option_cost
      #check to see if option was already added
      if option_name in self.option_ids:
        #just convert string to id number
        segment.option_id = self.option_ids[option_name]
      else:
        #need to add option to lists
        self.option_ids[option_name] = next_option_id
        self.option_names.append(option_name)
        self.option_costs.append(options_parsed[option_name])
        self.option_flags.append(False)
        self.option_set.append(False)
        #also convert string to id number
        segment.option_id = next_option_id
        next_option_id += 1

    #now tell about any declared options not used
    for option_name in options_parsed:
      if option_name not in self.option_ids:
        print "Option declared but not used:", option_name

def main():
  gdata = GameData()
  gdata.loadData()

  run = MetaRunSegments()
  run.loadFromFile("parsetest.txt", gdata)


  print "permutation count is", run.permutationCount()
  #run.printRun(gdata, True)

  import random
  max = run.permutationCount()
  seed = int(random.random() * max)

  created_run = run.makeRunSegments(seed)
  print "seed is", seed
  created_run.printRun()

  return

if __name__ == "__main__":
  main()


